home *** CD-ROM | disk | FTP | other *** search
/ PC Media 3 / PC MEDIA CD03.iso / share / prog / mrgsort / mrgsort.doc < prev    next >
Encoding:
Text File  |  1990-04-18  |  1.4 KB  |  33 lines
  1. UNIT mrgsort;
  2. (* By C.B. Falconer, public domain.  This is based on a description *)
  3. (* in Sedgewicks 'Algorithms', but modified for isolation to a TP   *)
  4. (* unit, with a generalized linkage to the items to sort.           *)
  5.  
  6. (* Since the 'info' field of a linknode is never used here, the     *)
  7. (* actual record may be designed as the application demands, so     *)
  8. (* long as the FIRST item in it is the 'next' pointer.  Care must   *)
  9. (* then be taken not to modify the info field of 'null'.            *)
  10.  
  11. (* The user defined 'greater' function will receive whatever type   *)
  12. (* of pointer is passed in to sort, and never the null pointer.     *)
  13.  
  14. (* The list to be sorted must be terminated with a 'next' that      *)
  15. (* contains the value 'null', and it must be the null defined here. *)
  16.  
  17. INTERFACE
  18.  
  19.   TYPE
  20.    greaterf     = FUNCTION(thing, than : pointer) : boolean;
  21.  
  22.   VAR
  23.     null        : pointer;   (* used as NIL substitute for end marks *)
  24.  
  25.   FUNCTION sort(root : pointer; greater : greaterf) : pointer;
  26.   (* This provides a logical level for passing in the 'greater' proc. *)
  27.   (* note that these procedures do not use the header link, i.e. the  *)
  28.   (* pointers they receive carry actual list data.  The pointers will *)
  29.   (* later be defined as holding only the next and an 'info' pointer. *)
  30.   (* The info pointer will not be used here, so can be of any type.   *)
  31.  
  32. IMPLEMENTATION
  33. j